|
Given a connected, undirected graph ''G'', a shortest-path tree rooted at vertex ''v'' is a spanning tree ''T'' of ''G'', such that the path distance from root ''v'' to any other vertex ''u'' in ''T'' is the shortest path distance from ''v'' to ''u'' in ''G''. In connected graphs where shortest paths are well-defined (i.e. where there are no negative-length cycles), we may construct a shortest-path tree using the following algorithm: # Compute dist(''u''), the shortest-path distance from root ''v'' to vertex ''u'' in ''G'' using Dijkstra's algorithm or Bellman–Ford algorithm. # For all non-root vertices ''u'', we can assign to ''u'' a parent vertex ''pu'' such that ''p''''u'' is connected to ''u'', and that dist(''p''''u'') + edge_dist(''p''''u'',''u'') = dist(''u''). In case multiple choices for ''pu'' exist, choose ''p''''u'' for which there exists a shortest path from ''v'' to ''p''''u'' with as few edges as possible; this tie-breaking rule is needed to prevent loops when there exist zero-length cycles. # Construct the shortest-path tree using the edges between each node and its parent. The above algorithm guarantees the existence of shortest-path trees. Like minimum spanning trees, shortest-path trees in general are not unique. In graphs for which all edges weights equal one, shortest path trees coincide with breadth-first search trees. In graphs that have negative cycles, the set of shortest simple paths from ''v'' to all other vertices do not necessarily form a tree. ==References== 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「Shortest-path tree」の詳細全文を読む スポンサード リンク
|